package com.atguigui.leetcode1;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

/**
 * 2569. 更新数组后处理求和查询
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/7/26 10:03
 */
public class P2569HandlingSumQueriesAfterUpdate {
    public static void main(String[] args) {

    }

    /*
        使用bitset
     */
    public long[] handleQuery1(int[] nums1, int[] nums2, int[][] queries) {

        int n = nums1.length;
        BitSet bitSet = new BitSet();
        for (int i = 0; i < n; i++) {
            if (nums1[i] == 1) {
                bitSet.set(i);
            }
        }

        // 求sums2的合
        long sum = 0;
        for (int x : nums2) {
            sum += x;
        }

        ArrayList<Long> ans = new ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 1) {
                bitSet.flip(q[1], q[2] + 1);
            } else if (q[0] == 2) {
                sum += (long) bitSet.cardinality() * q[1];
            } else {
                ans.add(sum);
            }
        }


        long[] res = new long[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }

        return res;
    }


    /*
        使用线段树
     */
    public long[] handleQuery2(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length;
        int m = queries.length;

        long sum = 0;
        for (int num : nums2) {
            sum += num;
        }

        List<Long> list = new ArrayList<Long>();
        //调用线段树
        SegTree tree = new SegTree(nums1);
        for (int i = 0; i < m; i++) {
            if (queries[i][0] == 1) {
                int l = queries[i][1];
                int r = queries[i][2];
                tree.reverseRange(l, r);
            } else if (queries[i][0] == 2) {
                sum += (long) tree.sumRange(0, n - 1) * queries[i][1];
            } else {
                list.add(sum);
            }
        }

        long[] ans = new long[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }

        return ans;
    }

    /*
        自定义线段树
     */
    class SegTree {
        private SegNode[] arr;

        public SegTree(int[] nums) {
            int n = nums.length;
            arr = new SegNode[n * 4 + 1];
            // 构建树
            build(1, 0, n - 1, nums);
        }

        public int sumRange(int left, int right) {
            return query(1, left, right);
        }

        // 反转
        public void reverseRange(int left, int right) {
            // 区间修改
            modify(1, left, right);
        }

        // 构建
        public void build(int id, int l, int r, int[] nums) {
            arr[id] = new SegNode();
            arr[id].l = l;
            arr[id].r = r;
            arr[id].lazytag = false;
            if (l == r) {
                arr[id].sum = nums[l];
                return;
            }
            // 除以2
            int mid = (l + r) >> 1;
            build(2 * id, l, mid, nums);
            build(2 * id + 1, mid + 1, r, nums);
            arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum;
        }

        /* pushdown函数：下传懒标记，即将当前区间的修改情况下传到其左右孩子结点 */
        public void pushdown(int x) {
            if (arr[x].lazytag) {
                arr[2 * x].lazytag = !arr[2 * x].lazytag;
                arr[2 * x].sum = arr[2 * x].r - arr[2 * x].l + 1 - arr[2 * x].sum;
                arr[2 * x + 1].lazytag = !arr[2 * x + 1].lazytag;
                arr[2 * x + 1].sum = arr[2 * x + 1].r - arr[2 * x + 1].l + 1 - arr[2 * x + 1].sum;
                arr[x].lazytag = false;
            }
        }

        /* 区间修改 */
        public void modify(int id, int l, int r) {
            // 判断是否在区间内
            if (arr[id].l >= l && arr[id].r <= r) {
                arr[id].sum = (arr[id].r - arr[id].l + 1) - arr[id].sum;
                // 反转后修改标签
                arr[id].lazytag = !arr[id].lazytag;
                return;
            }
            pushdown(id);
            int mid = (arr[id].l + arr[id].r) >> 1;
            if (arr[2 * id].r >= l) {
                modify(2 * id, l, r);
            }
            if (arr[2 * id + 1].l <= r) {
                modify(2 * id + 1, l, r);
            }
            arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum;
        }

        /* 区间查询 */
        public int query(int id, int l, int r) {
            if (arr[id].l >= l && arr[id].r <= r) {
                return arr[id].sum;
            }
            if (arr[id].r < l || arr[id].l > r) {
                return 0;
            }
            pushdown(id);
            int res = 0;
            if (arr[2 * id].r >= l) {
                res += query(2 * id, l, r);
            }
            if (arr[2 * id + 1].l <= r) {
                res += query(2 * id + 1, l, r);
            }
            return res;
        }
    }

    /*
        线段树的树节点
     */
    class SegNode {
        public int l, r, sum;
        // 标记是否是懒惰标记
        public boolean lazytag;

        public SegNode() {
            this.l = 0;
            this.r = 0;
            this.sum = 0;
            this.lazytag = false;
        }
    }

}



